#include "mergesort.h"
#include <QScopeGuard>

MergeSort::MergeSort(QObject *parent) : SortBase{parent}
{
    animation.setStartValue(0.0);
    animation.setEndValue(1.0);
    animation.setEasingCurve(QEasingCurve::OutQuart);
    animation.setLoopCount(1);
    connect(&animation, &QVariantAnimation::finished, &loop, &QEventLoop::quit);
    connect(&animation, &QVariantAnimation::valueChanged, this, &SortBase::updateRequest);
}

void MergeSort::sort(size_t num_of_elem, int interval)
{
    // ensure calling setRunState(false) and update at the end of function
    auto guard = qScopeGuard([this] {
        setRunState(false);
        emit updateRequest();
    });

    stop();
    if (arr.size() != num_of_elem)
        randomArray(num_of_elem);
    setRunState(true);

    this->interval = interval;
    MSort(0, (int) num_of_elem - 1);
}

void MergeSort::stop()
{
    setRunState(false);
    animation.stop();
    loop.quit();
    emit updateRequest();
}

void MergeSort::draw(QPainter *painter, int width, int height)
{
    painter->setPen(QColor(200, 200, 200));
    const size_t len = arr.size();
    const size_t max_elem = *(std::max_element(arr.begin(), arr.end()));

    // border
    constexpr int left_space = 0;
    constexpr int right_space = 0;
    constexpr int top_space = 20;
    constexpr int bottom_space = 50;

    // space width between two column
    constexpr int item_space = 10;

    const int text_height = painter->fontMetrics().height();

    // distance between column and number text
    constexpr int text_space = 15;

    // item width is dynamically adjusted according to the window width
    const double item_width = (width + item_space - left_space - right_space) / (double) len
                              - item_space;

    const double array_bottom = height / 2 - bottom_space;
    const double sub_array_bottom = height - bottom_space;

    // item height is also dynamically adjusted according to the window height
    const double height_factor = (height / 2 - top_space - bottom_space) / (double) max_elem;

    // current drawing column width and height
    double item_left = 0;
    double item_height = 0;
    double item_bottom = 0;

    QColor color;
    QString text;
    for (int i = 0; i < (int) len; i++) {
        // position of the column
        item_left = left_space + i * (item_width + item_space);
        item_height = height_factor * arr.at(i);
        item_bottom = array_bottom;
        text = QString::number(arr.at(i));

        // default color and text of the column
        color = QColor(200, 200, 200);

        // initializing sub array
        if (init_subArray) {
            if (i >= curr_low && i <= curr_high) {
                item_bottom += animation.currentValue().toDouble()
                               * (sub_array_bottom - array_bottom);
                if (i <= curr_mid) {
                    color = QColor(0, 170, 255);
                    item_height = height_factor * subArray_left.at(i - curr_low);
                    text = QString::number(subArray_left.at(i - curr_low));
                } else {
                    color = QColor(255, 170, 0);
                    item_height = height_factor * subArray_right.at(i - curr_mid - 1);
                    text = QString::number(subArray_right.at(i - curr_mid - 1));
                }
            }
        }
        // current comparing column
        else if (runState()) {
            // if already sorted then just draw
            if (i < curr_offset) {
                painter->drawText(item_left, item_bottom + text_height + text_space, text);
                painter->fillRect(item_left,
                                  item_bottom - item_height,
                                  item_width,
                                  item_height,
                                  color);
            }

            // draw subarray
            if (i >= curr_low && i <= curr_high) {
                item_bottom = sub_array_bottom;

                if (i >= curr_low + idx_left && i <= curr_mid) {
                    color = QColor(0, 170, 255);
                    item_height = height_factor * subArray_left.at(i - curr_low);
                    text = QString::number(subArray_left.at(i - curr_low));
                } else if (i <= curr_mid + idx_right) {
                    item_height = 0;
                    text.clear();
                } else {
                    color = QColor(255, 170, 0);
                    item_height = height_factor * subArray_right.at(i - curr_mid - 1);
                    text = QString::number(subArray_right.at(i - curr_mid - 1));
                }
            }

            // current min column
            if ((i == curr_low + idx_left - 1 && min_from == 0)
                || (i == curr_mid + idx_right && min_from == 1)) {
                item_bottom = sub_array_bottom
                              + animation.currentValue().toDouble()
                                    * (array_bottom - sub_array_bottom);
                item_left += animation.currentValue().toDouble() * (int) (curr_offset - i)
                             * (item_width + item_space);

                size_t min_val = (min_from == 0) ? subArray_left.at(idx_left - 1)
                                                 : subArray_right.at(idx_right - 1);
                item_height = height_factor * min_val;
                text = QString::number(min_val);
                color = QColor(0, 220, 0);
            }
        }

        // draw text
        painter->drawText(item_left, item_bottom + text_height + text_space, text);

        // draw rect
        painter->fillRect(item_left, item_bottom - item_height, item_width, item_height, color);
    }
}

void MergeSort::MSort(int front, int end)
{
    if (front >= end)
        return;

    int mid = (front + end) / 2;

    if (!runState())
        return;

    MSort(front, mid);

    if (!runState())
        return;

    MSort(mid + 1, end);

    if (!runState())
        return;

    merge(front, mid, end);
}

void MergeSort::merge(int front, int mid, int end)
{
    curr_low = front;
    curr_mid = mid;
    curr_high = end;

    // Copy Array[front ... mid] to SubArray_Left
    // Copy Array[mid+1 ... end] to SubArray_Right
    subArray_left.assign(arr.begin() + front, arr.begin() + mid + 1);
    subArray_right.assign(arr.begin() + mid + 1, arr.begin() + end + 1);
    init_subArray = true;
    wait(interval * 3);
    emit updateRequest();
    init_subArray = false;

    // prevent index out of bound
    subArray_left.push_back(std::numeric_limits<size_t>::max());
    subArray_right.push_back(std::numeric_limits<size_t>::max());

    // reset relevant index
    idx_left = 0, idx_right = 0;

    // Pick min of SubArray_Left[idxLeft] and SubArray_Right[idxRight], and put into Array[curr_offset]
    for (curr_offset = front; curr_offset <= end; curr_offset++) {
        if (subArray_left[idx_left] < subArray_right[idx_right]) {
            min_from = 0;
            arr[curr_offset] = subArray_left[idx_left];
            idx_left++;
        } else {
            min_from = 1;
            arr[curr_offset] = subArray_right[idx_right];
            idx_right++;
        }

        wait(interval * 3);
        emit updateRequest();
        min_from = -1;

        if (!runState()) {
            return;
        }
    }
}

void MergeSort::wait(int ms)
{
    // we use Eventloop to delay animation
    animation.setDuration(ms);
    animation.start();
    loop.exec();
}

void MergeSort::skip()
{
    this->interval = 1;
}
